class Solution {
public:
    int findMin(vector<int> &nums) {
        int n=nums.size();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        int numss[1000000]={0};
        for(int i=1;i<=n;i++){
            numss[i]=nums[i-1];
        }
        int s = sum / 2;
        vector<int> dp(s + 1, 0);
        for(int i=1;i<=n;i++){
            for(int j=s;j>=numss[i];j--){
                dp[j]=max(dp[j],dp[j-numss[i]]+numss[i]);
            }
        }
        return abs(dp[s]-(sum-dp[s]));
    }
};